package Leetcode.每日一题;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/3/27 16:34
 * @Description:
 * 给你一个二维整数数组 ranges ，其中 ranges[i] = [starti, endi] 表示 starti 到 endi 之间（包括二者）的所有整数都包含在第 i 个区间中。
 *
 * 你需要将 ranges 分成 两个 组（可以为空），满足：
 *
 * 每个区间只属于一个组。
 * 两个有 交集 的区间必须在 同一个 组内。
 * 如果两个区间有至少 一个 公共整数，那么这两个区间是 有交集 的。
 *
 * 比方说，区间 [1, 3] 和 [2, 5] 有交集，因为 2 和 3 在两个区间中都被包含。
 * 请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大，将它对 109 + 7 取余 后返回。
 *
 *
 *
 * 示例 1：
 *
 * 输入：ranges = [[6,10],[5,15]]
 * 输出：2
 * 解释：
 * 两个区间有交集，所以它们必须在同一个组内。
 * 所以有两种方案：
 * - 将两个区间都放在第 1 个组中。
 * - 将两个区间都放在第 2 个组中。
 * 示例 2：
 *
 * 输入：ranges = [[1,3],[10,20],[2,5],[4,8]]
 * 输出：4
 * 解释：
 * 区间 [1,3] 和 [2,5] 有交集，所以它们必须在同一个组中。
 * 同理，区间 [2,5] 和 [4,8] 也有交集，所以它们也必须在同一个组中。
 * 所以总共有 4 种分组方案：
 * - 所有区间都在第 1 组。
 * - 所有区间都在第 2 组。
 * - 区间 [1,3] ，[2,5] 和 [4,8] 在第 1 个组中，[10,20] 在第 2 个组中。
 * - 区间 [1,3] ，[2,5] 和 [4,8] 在第 2 个组中，[10,20] 在第 1 个组中。
 *
 *
 * 提示：
 *
 * 1 <= ranges.length <= 105
 * ranges[i].length == 2
 * 0 <= starti <= endi <= 109
 */

public class 统计将重叠区间合并成组的方案数 {
    // 定义一个常量MOD，其值为1000000007，这是一个常用的质数，用于取模运算
    static final int MOD = 1000000007;

    public int countWays(int[][] ranges) {
        // 对输入的二维数组 ranges 根据第一个元素进行排序
        Arrays.sort(ranges, (a, b) -> a[0] - b[0]);
        int n = ranges.length; // 获取排序后数组的长度
        int res = 1; // 初始化结果变量res为1，因为最终结果需要对MOD取模，所以从1开始计算
        for (int i = 0; i < n; ) {
            int r = ranges[i][1]; // 初始化一个变量r，表示当前区间的右端点
            int j = i + 1; // 初始化一个变量j，表示下一个区间的起始位置
            // 当j小于数组长度，并且下一个区间的左端点小于等于当前区间的右端点时，进行循环
            while (j < n && ranges[j][0] <= r) {
                // 更新r的值为当前区间和下一个区间的右端点的最大值
                r = Math.max(r, ranges[j][1]);
                j++; // j向后移动
            }
            // 根据当前区间的长度（r - ranges[i][0] + 1），计算出当前区间内的可能组合数，
            // 然后将结果乘以2（因为每个区间都可以选择包含或不包含），并对MOD取模
            res = res * (r - ranges[i][0] + 1) % MOD;
            i = j; // 将i更新为j的位置，准备进入下一轮循环
        }
        return res; // 返回计算结果
    }

}
